package com.peng.old.sort;


import com.peng.old.util.SortUtil;

import java.util.Arrays;

/**
 * 插入排序
 */
public class InsertSort {

    public static void main(String[] args) {
        int[] arr = new int[]{3, 5, 1, 8, 9, 20, 24, 7, 3, 2};
//        int[] ints = SortUtil.makeRandomArray(1000);
        test2(arr);
//        System.out.println(SortUtil.checkResult(ints));


        System.out.println(Arrays.toString(arr));

    }

    public static void test1(int[] arr){

        //将数组比作是一副扑克牌， 从第一张开始抽出，与之前的进行比较，插入
        for (int i = 1; i < arr.length; i++) {

            for (int j = i; j >0; j--) {
                if(arr[j]<arr[j-1]){
                    SortUtil.swap(arr,j,j-1);
                }

            }


        }

    }

    /**
     * 优化
     * @param arr
     */
    public static void test2(int[] arr){

        //将数组比作是一副扑克牌， 从第一张开始抽出，与之前的进行比较，插入
        for (int i = 1; i < arr.length; i++) {
            //保存当前"牌"
            int destNum = arr[i];
            int j = i;
            //将当前"牌"与前面的挨个比较，比当前"牌"大的，依次向后移动
            for (; j >0&&destNum<arr[j-1]; j--) {
                arr[j] = arr[j-1];
            }
            arr[j] = destNum;


        }

    }
}
